package Search.BST;


/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/11/13 9:23
 */

/*
关于搜索树的类

验证该对象的合法性：
1. size >= 0
2. size 和 root 之间的关系
   size == 通过遍历(root)得到的结点个数
3. root 维护的树需要是搜索树：任取结点 bla bla
   中序遍历是有序的（key 不重复） <=> 搜索树的规则
   搜索树 => 中序是有序的
   中序是有序 => 搜索树
 */
public class BSTree {
    private TreeNode root;
    private int size;

    public BSTree() {
        this.root = null;
        size = 0;
    }


    //查找
    public boolean contains(long key) {
        TreeNode cur = root;

        while (cur != null) {
            if (key == cur.key) {
                return true;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return false;
    }

    //插入
    //插入过程中有可能失败 （key 重复）
    public boolean add(long key) {
        TreeNode node = new TreeNode(key);
        if (this.root == null) {
            this.root = node;
            size++;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;

        while (cur != null) {
            if (key == cur.key) {
                return false;
            } else if (key > cur.key) {
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        // cur == null
        // 保证 parent 一定是 cur 的双亲
        // 断言 parent != null
        // 要做的工作，把 node 插入到 parent 的孩子中
        if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        this.size++;

        return true;

    }


    // 删除的操作
    public boolean remove(long key) {
        TreeNode parent = null;
        TreeNode cur = root;

        while (cur != null) {
            if (key == cur.key) {
                deleteNode(parent, cur);    // parent == null
                this.size--;
                return true;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                // key > cur.key
                parent = cur;
                cur = cur.right;
            }
        }

        return false;
    }

    private void deleteNode(TreeNode parent, TreeNode node) {
        if (node.left == null) {
            if (node == this.root) {    // parent == null
                this.root = node.right;
            } else if (parent.left == node) {
                parent.left = node.right;
            } else {
                // parent.right == node
                parent.right = node.right;
            }
        } else if (node.right == null) {
            if (node == this.root) {    // parent == null
                this.root = node.left;
            } else if (parent.left == node) {
                parent.left = node.left;
            } else {
                // parent.right == node
                parent.right = node.left;
            }
        } else {
            // node.left != null && node.right != null
            // 采用替换删除的方式
            // 此处选择右子树中最小的一个（即右子树中最左的一个）
            TreeNode toDeleteParent = node;
            TreeNode toDelete = node.right;
            // 断言：toDelete != null
            // 一路朝左走（toDelete.left == null 停下来）
            while (toDelete.left != null) {
                toDeleteParent = toDelete;
                toDelete = toDelete.left;
            }

            // toDelete 是我们要删除的结点
            node.key = toDelete.key;

            // 删除 toDelete
            // 断言：toDelete.left == null
            // 断言：toDelete != this.root
            // toDeleteParent.left | right = toDelete.right
            // toDeleteParent == node => 断言 toDeleteParent.right == toDelete
            //                  else  => 断言 toDeleteParent.left == toDelete
            if (toDeleteParent.left == toDelete) {
                toDeleteParent.left = toDelete.right;
            } else {
                // toDeleteParent.right == toDelete
                toDeleteParent.right = toDelete.right;
            }
        }
    }

    public static void main(String[] args) {
        BSTree tree = new BSTree();
        long[] keys = { 5, 1, 6, 8, 3, 9, 0, 2, 4, 7 };
        for (long key : keys) {
            tree.add(key);
        }

        System.out.println(tree.remove(1));
    }
}